package top.lshaci.learning.algorithm;

import java.util.Arrays;

/**
 * BinaryHeapPriorityQueue
 * <p>
 * 二叉堆(最大堆: 堆顶元素值最大) - 优先队列
 *
 * @author liangxu
 */
public class BinaryHeapPriorityQueue {

    private int[] array;

    private int size;

    public BinaryHeapPriorityQueue() {
        // 队列初始化长度为32
        array = new int[32];
    }

    /**
     * 入队
     *
     * @param key 入队元素
     */
    public void enQueue(int key) {
        // 队列长度超出范围, 扩容
        if (size >= array.length) {
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     *
     * @return 出队元素
     * @throws Exception 队列为空抛出
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("队列已空");
        }
        int head = array[0];
        array[0] = array[size - 1];
        array[size - 1] = head;
        downAdjust();
        return head;
    }

    /**
     * "上浮"调整
     */
    public void upAdjust() {
        int childIndex = this.size - 1;
        int parentIndex = (childIndex - 1) / 2;
        // temp 保存插入的叶子节点值, 用于最后赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp > array[parentIndex]) {
            // 无须真正交换, 单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * "下沉"调整
     */
    private void downAdjust() {
        int parentIndex = 0;
        // temp 保存父节点值, 用于最后赋值
        int temp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size) {
            // 如果存在右节点, 并且右节点的值大于左节点, 则定位到右节点
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任何一个子节点的值, 直接跳出
            if (temp > array[childIndex]) {
                break;
            }
            // 交换父节点和子节点的值
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 队列扩容
     */
    private void resize() {
        // 队列容量翻倍
        int newSize = array.length * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    public static void main(String[] args) throws Exception {
        BinaryHeapPriorityQueue queue = new BinaryHeapPriorityQueue();
        queue.enQueue(3);
        queue.enQueue(5);
        queue.enQueue(10);
        queue.enQueue(2);
        queue.enQueue(7);
        System.err.println("出队元素: " + queue.deQueue());
        System.err.println("出队元素: " + queue.deQueue());
    }
}
